ଘ(੭ˊ꒳ ˋ)੭✧˙˚
嗨，我是wec，今天是DAY 14。

🔎 題目難度與描述

難度：MEDIUM

題目描述：

給定一個二元樹，找出其最小深度。
1.最小深度：從根節點到最近葉子節點的最短路徑上的節點數。
2.葉子節點：沒有子節點的節點。

🔎 解題思路＆程式碼

1️⃣ 遞迴

第1步： 如果節點為nil（空節點），直接返回 0，表示沒有深度。
第2步： 處理只有一邊的情況：
1.如果左子樹為空，選擇右子樹，計算右子樹的深度並加 1。
2.如果右子樹為空，選擇左子樹，計算左子樹的深度並加 1。
第3步： 處理兩邊都存在的情況：遞迴計算左右子樹的深度，選擇較小的深度並加 1，得到從根節點到最近葉子節點的最小深度。
程式碼：

def min_depth(root)
  return 0 if root.nil?

  return min_depth(root.right) + 1 if root.left.nil?
  return min_depth(root.left) + 1 if root.right.nil?

  [min_depth(root.left), min_depth(root.right)].min + 1
end

🔎 總結

時間複雜度

遞迴法： 時間複雜度為O(n)，n為節點數量。
➡️ 這題跟maximum比起來稍微複雜一點，需要注意到兩邊子樹可能有其中邊為空的情況，不能再做簡單的判斷，因為如果直接取了左右子樹的最小值，就會得到錯誤的答案喔!!

那麽，以上就是今天的內容！

相信IT人動腦時都要吃點東西，所以今天邊寫邊吃魷魚乾。
明天要說：Ruby精選刷題！Medium路跑D-7(>∀･)⌒☆